package 力扣链表;

public class Leetcode206反转链表 {

    //方法1：临时节点
    public static ListNode reverseList2(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        //方法1.临时节点
        ListNode prev = new ListNode();
        //链表的第一个节点已经在新链表中
        prev.next = null;
        while (head != null){
            //开始执行新的链表
            ListNode temp = head.next;
            head.next = prev.next;
            prev.next = head;
            head = temp;
        }
        return prev.next;
    }
    //方法2：三指针
    public ListNode reverseList1(ListNode head) {
        if (head == null || head.next == null){
            return head;
        }
        ListNode prev = new ListNode();
        ListNode sec = head;
        while (sec != null){
            ListNode temp = sec.next;
            sec.next = prev;
            prev = sec;
            sec = temp;
        }
        return prev;
    }
    //方法3:递归
    /**
     * 哥你一你个单链表，你就能将链表反转，并返回头节点
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        //1递归终止条件
        if (head == null || head.next == null) {
            return head;
        }
        //保存第二个节点的地址
        ListNode temp = head.next;
        //将第二节点以后反转，得到新头节点
        ListNode node = reverseList(head.next);
        //让第二个节点的next指向head
        temp.next = head;
        //消除环
        head.next = null;
        //2得到剩余节点逆转后的链表，
        return node;
    }
}
